// 实现环形数组


// 原本以数组的特点，其是一块连续的内存空间，不可能是环形的。 但可以通过一些代码实现

let arr = [1,2,3,4,5];

let i = 0

while (i < arr.length) {
    console.log(arr[i])
    i = (i + 1) % arr.length
}
//  当i 到达数组的末尾时， 对数组长度取模 为0，即回到数组的头部

// 利用这个技巧 可以帮助我们 在o(1)复杂度下 在数组头部插入数据

// 环形数组  将设计成左闭右开的方式，是为了便于边界处理
// start = end = 0 区间[0,0) 中没有元素，只要让end 向右移动一位，区间就包含一个元素0

class circleArray {
    constructor(size = 1) {
        this.capcity = size // 环形数组的容量 固定不变
        this.count = 0;    // 实际的存在的元素数量  变化的
        // 左闭右开的结构
        this.start = 0; // 始终指向第一个有效元素  如 当前 第一个正在用餐的人的座位
        this.end = 0   // 常见 指向下一个可插入元素的位置  如下一个新来的人可坐的位置
        this.arr = new Array(size)   // 实际操作的数组，指一个环形座位

    }
    //
    resize(newSize){
        let newArr = new Array(newSize)

        //  转移数据
        for(let i =0;i<this.count;i++) {
            newArr[i] = this.arr[(this.size + i) % this.size]
        }
        this.arr = newArr
        // 重置 start 和end 指针
        this.end = this.count
        this.start = 0
        this.size = newSize
    }
    //  在数组头部添加元素 时间复杂度O(1)
    addFirst(val){
        // 数组满时 扩容为原来的2倍
        if(this.isFull()) {
            this.resize(this.capcity * 2)
        }
        //start 是闭区间 先左移 再赋值
        this.start = (this.start - 1 + this.capcity) % this.capcity
        this.arr[this.start] = val
        this.count++
    }
    isFull() {
        return this.size >= this.count
    }
    isEmpty() {
        return this.count ===0
    }
    // 删除头部元素 时间复杂度O(1)
    removeFirst() {
        if(this.isEmpty()) {
            throw new Error('this array is empty');
        }
        //  删除头部的元素
        this.arr[this.start] = null
        this.start = (this.start + 1) % this.capcity
        this.count--;
    }
    addLast(val) {
        if(this.isFull()) {
            this.resize(this.capcity * 2)
        }
        this.arr[this.end] = val
        this.end = (this.end + 1) % this.capcity
        this.count++
    }
    removeLast() {
        if(this.isEmpty()) {
            throw new Error('this array is empty');
        }
        // end是开区间 所以先左移 再赋值
        this.end = (this.end -1 + this.capcity) % this.capcity
        this.arr[this.end] = null
        this.count--;
        //  删除元素时 顺便进行缩容
        if(this.count > 0 && this.count === (this.capcity / 4)) {
            this.resize(this.capcity / 2)
        }
    }
    //获取头部元素
    getFirst() {
        if(this.isEmpty()) {
            throw new Error('this array is empty');
        }
        return this.arr[this.start];
    }
    getLast() {
        if(this.isEmpty()) {
            throw new Error('this array is empty');
        }
        return this.arr[(this.end - 1 + this.capcity) % this.capcity];
    }
}

// 总结：
// 环形数组 利用对数组大小进行取模，巧妙的 实现了 对数组头/尾 的删除/增加元素操作时
// 时间复杂度变为O(1)
// 但在对中间某个索引位置的元素进行操作，其时间复杂度仍然为O(n)

// 可以这样理解环形数组：
// 一个环形餐桌，start指向当前用餐的人的位置  end指向下一个新来的人可以坐的座位
// 如每个座位0-7 共8个位置，capacity 座位数是固定
// 若当前有三个人， A 0 B 1 C 2  要在头部增加元素，就是在A的前面，由于是环形的那么A的右边
// 是7号位置， 新来的人坐在7号，此时start指向它，它就是首位 此时7->0->1->2